{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Markov Decision Process in the World 6x6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Environment World"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](6x6_states.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Construct states, actions and rewards\n",
    "### List of states: 6x6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'list'>\n",
      "[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)]\n"
     ]
    }
   ],
   "source": [
    "states = []\n",
    "for x in range(6):\n",
    "    for y in range(6):\n",
    "        states.append((x, y))        \n",
    "print(type(states))\n",
    "print(states)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dict of actions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'dict'>\n",
      "{'U': (-1, 0), 'L': (0, -1), 'D': (1, 0), 'R': (0, 1)}\n"
     ]
    }
   ],
   "source": [
    "actions = {\"R\": (0,1), \"L\":(0,-1), \"U\":(-1,0), \"D\":(1,0)}\n",
    "print(type(actions))\n",
    "print(actions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Rewards for usual fields (-1), bad fields (-2) and the target (10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'dict'>\n",
      "Rewards for usual fields:  {'(0 4)': -1, '(0 3)': -1, '(3 1)': -1, '(4 4)': -1, '(5 2)': -1, '(0 2)': -1, '(2 2)': -1, '(1 1)': -1, '(2 4)': -1, '(5 0)': -1, '(1 3)': -1, '(3 5)': -1, '(1 5)': -1, '(1 2)': -1, '(3 2)': -1, '(4 3)': -1, '(2 3)': -1, '(3 4)': -1, '(1 4)': -1, '(5 5)': -1, '(2 1)': -1, '(4 0)': -1, '(4 2)': -1, '(0 1)': -1, '(0 0)': -1, '(3 0)': -1, '(1 0)': -1, '(2 0)': -1, '(5 3)': -1, '(2 5)': -1, '(0 5)': -1, '(5 4)': -1, '(4 5)': -1, '(4 1)': -1, '(3 3)': -1, '(5 1)': -1}\n"
     ]
    }
   ],
   "source": [
    "rewards = {\"({} {})\".format(*s): -1 for s in states} \n",
    "print(type(rewards))\n",
    "print('Rewards for usual fields: ', rewards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'(0 4)': -1, '(0 3)': -1, '(3 1)': -1, '(4 4)': -2, '(5 2)': -2, '(0 2)': -1, '(2 2)': -1, '(1 1)': -2, '(2 4)': -1, '(5 0)': -2, '(1 3)': -2, '(3 5)': -1, '(1 5)': -1, '(1 2)': -1, '(3 2)': -1, '(4 3)': -1, '(2 3)': -2, '(3 4)': -2, '(1 4)': -1, '(5 5)': 10, '(2 1)': -1, '(4 0)': -1, '(4 2)': -2, '(0 1)': -2, '(0 0)': -1, '(3 0)': -2, '(1 0)': -1, '(2 0)': -1, '(5 3)': -1, '(2 5)': -1, '(0 5)': -2, '(5 4)': -1, '(4 5)': -1, '(4 1)': -1, '(3 3)': -1, '(5 1)': -1}\n",
      "dict_keys(['(0 4)', '(0 3)', '(3 1)', '(4 4)', '(5 2)', '(0 2)', '(2 2)', '(1 1)', '(2 4)', '(5 0)', '(1 3)', '(3 5)', '(1 5)', '(1 2)', '(3 2)', '(4 3)', '(2 3)', '(3 4)', '(1 4)', '(5 5)', '(2 1)', '(4 0)', '(4 2)', '(0 1)', '(0 0)', '(3 0)', '(1 0)', '(2 0)', '(5 3)', '(2 5)', '(0 5)', '(5 4)', '(4 5)', '(4 1)', '(3 3)', '(5 1)'])\n",
      "<class 'dict_keys'>\n",
      "key:  (0 4) , reward:  -1\n",
      "key:  (0 3) , reward:  -1\n",
      "key:  (3 1) , reward:  -1\n",
      "key:  (4 4) , reward:  -2\n",
      "key:  (5 2) , reward:  -2\n",
      "key:  (0 2) , reward:  -1\n",
      "key:  (2 2) , reward:  -1\n",
      "key:  (1 1) , reward:  -2\n",
      "key:  (2 4) , reward:  -1\n",
      "key:  (5 0) , reward:  -2\n",
      "key:  (1 3) , reward:  -2\n",
      "key:  (3 5) , reward:  -1\n",
      "key:  (1 5) , reward:  -1\n",
      "key:  (1 2) , reward:  -1\n",
      "key:  (3 2) , reward:  -1\n",
      "key:  (4 3) , reward:  -1\n",
      "key:  (2 3) , reward:  -2\n",
      "key:  (3 4) , reward:  -2\n",
      "key:  (1 4) , reward:  -1\n",
      "key:  (5 5) , reward:  10\n",
      "key:  (2 1) , reward:  -1\n",
      "key:  (4 0) , reward:  -1\n",
      "key:  (4 2) , reward:  -2\n",
      "key:  (0 1) , reward:  -2\n",
      "key:  (0 0) , reward:  -1\n",
      "key:  (3 0) , reward:  -2\n",
      "key:  (1 0) , reward:  -1\n",
      "key:  (2 0) , reward:  -1\n",
      "key:  (5 3) , reward:  -1\n",
      "key:  (2 5) , reward:  -1\n",
      "key:  (0 5) , reward:  -2\n",
      "key:  (5 4) , reward:  -1\n",
      "key:  (4 5) , reward:  -1\n",
      "key:  (4 1) , reward:  -1\n",
      "key:  (3 3) , reward:  -1\n",
      "key:  (5 1) , reward:  -1\n",
      "State:  (0 0) , key:  (0 0) , Reward:  -1\n",
      "State:  (0 1) , key:  (0 1) , Reward:  -2\n",
      "State:  (0 2) , key:  (0 2) , Reward:  -1\n",
      "State:  (0 3) , key:  (0 3) , Reward:  -1\n",
      "State:  (0 4) , key:  (0 4) , Reward:  -1\n",
      "State:  (0 5) , key:  (0 5) , Reward:  -2\n",
      "State:  (1 0) , key:  (1 0) , Reward:  -1\n",
      "State:  (1 1) , key:  (1 1) , Reward:  -2\n",
      "State:  (1 2) , key:  (1 2) , Reward:  -1\n",
      "State:  (1 3) , key:  (1 3) , Reward:  -2\n",
      "State:  (1 4) , key:  (1 4) , Reward:  -1\n",
      "State:  (1 5) , key:  (1 5) , Reward:  -1\n",
      "State:  (2 0) , key:  (2 0) , Reward:  -1\n",
      "State:  (2 1) , key:  (2 1) , Reward:  -1\n",
      "State:  (2 2) , key:  (2 2) , Reward:  -1\n",
      "State:  (2 3) , key:  (2 3) , Reward:  -2\n",
      "State:  (2 4) , key:  (2 4) , Reward:  -1\n",
      "State:  (2 5) , key:  (2 5) , Reward:  -1\n",
      "State:  (3 0) , key:  (3 0) , Reward:  -2\n",
      "State:  (3 1) , key:  (3 1) , Reward:  -1\n",
      "State:  (3 2) , key:  (3 2) , Reward:  -1\n",
      "State:  (3 3) , key:  (3 3) , Reward:  -1\n",
      "State:  (3 4) , key:  (3 4) , Reward:  -2\n",
      "State:  (3 5) , key:  (3 5) , Reward:  -1\n",
      "State:  (4 0) , key:  (4 0) , Reward:  -1\n",
      "State:  (4 1) , key:  (4 1) , Reward:  -1\n",
      "State:  (4 2) , key:  (4 2) , Reward:  -2\n",
      "State:  (4 3) , key:  (4 3) , Reward:  -1\n",
      "State:  (4 4) , key:  (4 4) , Reward:  -2\n",
      "State:  (4 5) , key:  (4 5) , Reward:  -1\n",
      "State:  (5 0) , key:  (5 0) , Reward:  -2\n",
      "State:  (5 1) , key:  (5 1) , Reward:  -1\n",
      "State:  (5 2) , key:  (5 2) , Reward:  -2\n",
      "State:  (5 3) , key:  (5 3) , Reward:  -1\n",
      "State:  (5 4) , key:  (5 4) , Reward:  -1\n",
      "State:  (5 5) , key:  (5 5) , Reward:  10\n"
     ]
    }
   ],
   "source": [
    "rewards[\"(0 1)\"] = -2\n",
    "rewards[\"(0 5)\"] = -2\n",
    "rewards[\"(1 1)\"] = -2\n",
    "rewards[\"(1 3)\"] = -2\n",
    "rewards[\"(2 3)\"] = -2\n",
    "rewards[\"(3 0)\"] = -2\n",
    "rewards[\"(3 4)\"] = -2\n",
    "rewards[\"(4 2)\"] = -2\n",
    "rewards[\"(4 4)\"] = -2\n",
    "rewards[\"(5 0)\"] = -2\n",
    "rewards[\"(5 2)\"] = -2\n",
    "rewards[\"(5 5)\"] = 10\n",
    "\n",
    "print(rewards)\n",
    "\n",
    "print(rewards.keys())\n",
    "print(type(rewards.keys()))\n",
    "\n",
    "for i in rewards.keys():\n",
    "     print( 'key: ', i, ', reward: ', rewards.get(i) )\n",
    "\n",
    "for i in  range(0,6):\n",
    "    for j in range(0,6):\n",
    "        st = '(' + str(i) + ' ' + str(j) + ')'\n",
    "        key = str(st)\n",
    "        print( 'State: ', st, ', key: ', key, ', Reward: ', rewards.get(key))  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Construct  Transitions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'dict'>\n",
      "{'(0 4)': {}, '(0 3)': {}, '(3 1)': {}, '(4 4)': {}, '(5 2)': {}, '(0 2)': {}, '(2 2)': {}, '(1 1)': {}, '(2 4)': {}, '(5 0)': {}, '(1 3)': {}, '(3 5)': {}, '(1 5)': {}, '(1 2)': {}, '(3 2)': {}, '(4 3)': {}, '(2 3)': {}, '(3 4)': {}, '(1 4)': {}, '(5 5)': {}, '(2 1)': {}, '(4 0)': {}, '(4 2)': {}, '(0 1)': {}, '(0 0)': {}, '(3 0)': {}, '(1 0)': {}, '(2 0)': {}, '(5 3)': {}, '(2 5)': {}, '(0 5)': {}, '(5 4)': {}, '(4 5)': {}, '(4 1)': {}, '(3 3)': {}, '(5 1)': {}}\n"
     ]
    }
   ],
   "source": [
    "transitions = {\"({} {})\".format(*state): {} for state in states} \n",
    "print(type(transitions))\n",
    "print(transitions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a:  [0.1, '(1 4)']\n"
     ]
    }
   ],
   "source": [
    "def build_actions(state, prob):\n",
    "    return[prob, \"({} {})\".format(*state)]\n",
    "a = build_actions(states[10], 0.1)           \n",
    "print('a: ', a)   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let the agent be in the cell (0,0). If the agent should get the action=**Up**, then he has 10% chance of going down, 10% of going left and 80% chance of remaining in place because the  agent cannot go up from this cell. The same for the action=**Left** because the agent cannot go left from the cell=(0,0). Assume the agent is in the cell=(0,3), and the action=**Up**.\n",
    "Then the agent has 10% chance of going down, 10% of going left, 10% of going right and 70% chance of \n",
    "remaining in  place because the  agent cannot go up from this cell. For the action=**Left** \n",
    "he has 10% chance of going down, of going right, of remaining in place and 70% chance of going left.\n",
    "For each action out {**Up**, **Left**, **Right**, **Down**}, the probabilties of going to one of 4\n",
    "cells or of remaining in place are given in the following picture.  Here, the **transitions rules** are given almost for any cell (but not for all). For remaining cells, the **transitions rules**\n",
    "are similarly given.\n",
    "\n",
    "![](actions_from_cell.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## Example: transitions for specific state \n",
    " \n",
    " **How the algorithm builds transitions?**\n",
    " \n",
    " **(1) Just sum (i.e., result)  = state + actions[action]**     \n",
    "\n",
    "   u_sum = [sum(x) for x in zip(state, actions[action])]   \n",
    "   \n",
    "   sum(x) = state + actions[action]\n",
    "   \n",
    " **(2) State = states[9] = (1 3) + any action**\n",
    "      \n",
    "   Let state  = (1 3), then\n",
    "\n",
    "   (1 3) + Up = (1 3) + (-1 0) = (0 3)   \n",
    "   (1 3) + Right = (1 3) + (0 1) = (1,4)   \n",
    "   (1 3) + Left = (1 3) + (0 -1) = (1 2)   \n",
    "   (1 3) + Down = (1 3) + (1 0) = (2 3)   \n",
    "\n",
    " **(3) State = states[10] = (1 4) + any action**\n",
    " \n",
    "   For the state = (1 4), we have   \n",
    "   \n",
    "   (1 4) + Up = (1 4) + (-1 0) = (0 4)   \n",
    "   (1 4) + Right = (1 4) + (0 1) = (1 5)   \n",
    "   (1 4) + Left = (1 4) + (0 -1) = (1 3)    \n",
    "   (1 4) + Down = (1 4) + (1 0) = (2 4)   \n",
    "   \n",
    "   **(4) What is T[0][0] before before and update?**\n",
    "   \n",
    "   For the transition T = [[0.0, '(0 3)'], [0.1, '(1 3)'], [0.1, '(1 4)'], [0.1, '(1 2)'], [0.1, '(2 3)']]  \n",
    "   we have that T[0][0] =  0.0 , T[0][1] =  (0 3) ,  T[1][0] = 0.1, T[1][1] = (1 3), ...\n",
    "   \n",
    "   \n",
    "   If count = 0.4, after the update T[0][0] = 1.0 - count, we get       \n",
    "   T = [[0.6, '(0 3)'], [0.1, '(1 3)'], [0.1, '(1 4)'], [0.1, '(1 2)'], [0.1, '(2 3)']]  \n",
    "   \n",
    "   \n",
    "   **(5) Function build_actions**\n",
    "   \n",
    "   For result = (0 3), build_actions(result, 0.0) returns [0.0, '(0 3)'].   \n",
    "   For state = (1 3),  build_actions(state, 0.1) returns [0.1, '(1 3)'].\n",
    "    \n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "state:  (1, 3) , action:  U , transitions:  [[0.6, '(0 3)'], [0.1, '(1 3)'], [0.1, '(1 2)'], [0.1, '(2 3)'], [0.1, '(1 4)']]\n",
      "state:  (1, 3) , action:  L , transitions:  [[0.6, '(1 2)'], [0.1, '(1 3)'], [0.1, '(0 3)'], [0.1, '(2 3)'], [0.1, '(1 4)']]\n",
      "state:  (1, 3) , action:  D , transitions:  [[0.6, '(2 3)'], [0.1, '(1 3)'], [0.1, '(0 3)'], [0.1, '(1 2)'], [0.1, '(1 4)']]\n",
      "state:  (1, 3) , action:  R , transitions:  [[0.6, '(1 4)'], [0.1, '(1 3)'], [0.1, '(0 3)'], [0.1, '(1 2)'], [0.1, '(2 3)']]\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    " format of transitions:\n",
    " (x,y) = {\"R: [prob, (x1, y1)]\"}\n",
    "'''\n",
    "state=states[9]# (1 3)\n",
    "#state=states[10] (1 4)\n",
    "#print('state: ', state)\n",
    "\n",
    "for action in actions:\n",
    "        count = 0.0\n",
    "        # just sum = state + actions[action]\n",
    "        # u_sum = [sum(x) for x in zip(state, actions[action])]\n",
    "        result = tuple(( sum(x) for x in zip(state, actions[action]))  )        \n",
    "        # transitions\n",
    "        # print('state: ', state, ', action: ', actions[action], ', u_sum: ', u_sum, ', result', result)\n",
    "        T = []\n",
    "        if result in states:\n",
    "            T.append(build_actions(result, 0.0))\n",
    "            T.append(build_actions(state, 0.1))\n",
    "            # for any action (if result in the state space) we increase count  \n",
    "            count += 0.1  \n",
    "        else:\n",
    "            T.append(build_actions(state, 0.0)) \n",
    "            \n",
    "        for a in actions:\n",
    "            if (a != action):\n",
    "                result2 = tuple( (sum(x) for x in zip(state, actions[a])) ) \n",
    "                #print('result2: ', result2, ', a: ', a, ', action: ', action)\n",
    "                if result2 in states:\n",
    "                    count += 0.1\n",
    "                    T.append(build_actions(result2, 0.1))\n",
    "        T[0][0] = 1.0 - count\n",
    "        \n",
    "        transitions[\"({} {})\".format(*state)][action] = T\n",
    "        print('state: ', state, ', action: ', action, ', transitions: ', T)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "state:  (0, 0) , action:  U , transitions:  [[0.8, '(0 0)'], [0.1, '(1 0)'], [0.1, '(0 1)']]\n",
      "state:  (0, 0) , action:  L , transitions:  [[0.8, '(0 0)'], [0.1, '(1 0)'], [0.1, '(0 1)']]\n",
      "state:  (0, 0) , action:  D , transitions:  [[0.8, '(1 0)'], [0.1, '(0 0)'], [0.1, '(0 1)']]\n",
      "state:  (0, 0) , action:  R , transitions:  [[0.8, '(0 1)'], [0.1, '(0 0)'], [0.1, '(1 0)']]\n",
      "state:  (0, 1) , action:  U , transitions:  [[0.7, '(0 1)'], [0.1, '(0 0)'], [0.1, '(1 1)'], [0.1, '(0 2)']]\n",
      "state:  (0, 1) , action:  L , transitions:  [[0.7, '(0 0)'], [0.1, '(0 1)'], [0.1, '(1 1)'], [0.1, '(0 2)']]\n",
      "state:  (0, 1) , action:  D , transitions:  [[0.7, '(1 1)'], [0.1, '(0 1)'], [0.1, '(0 0)'], [0.1, '(0 2)']]\n",
      "state:  (0, 1) , action:  R , transitions:  [[0.7, '(0 2)'], [0.1, '(0 1)'], [0.1, '(0 0)'], [0.1, '(1 1)']]\n",
      "state:  (0, 2) , action:  U , transitions:  [[0.7, '(0 2)'], [0.1, '(0 1)'], [0.1, '(1 2)'], [0.1, '(0 3)']]\n",
      "state:  (0, 2) , action:  L , transitions:  [[0.7, '(0 1)'], [0.1, '(0 2)'], [0.1, '(1 2)'], [0.1, '(0 3)']]\n",
      "state:  (0, 2) , action:  D , transitions:  [[0.7, '(1 2)'], [0.1, '(0 2)'], [0.1, '(0 1)'], [0.1, '(0 3)']]\n",
      "state:  (0, 2) , action:  R , transitions:  [[0.7, '(0 3)'], [0.1, '(0 2)'], [0.1, '(0 1)'], [0.1, '(1 2)']]\n",
      "state:  (0, 3) , action:  U , transitions:  [[0.7, '(0 3)'], [0.1, '(0 2)'], [0.1, '(1 3)'], [0.1, '(0 4)']]\n",
      "state:  (0, 3) , action:  L , transitions:  [[0.7, '(0 2)'], [0.1, '(0 3)'], [0.1, '(1 3)'], [0.1, '(0 4)']]\n",
      "state:  (0, 3) , action:  D , transitions:  [[0.7, '(1 3)'], [0.1, '(0 3)'], [0.1, '(0 2)'], [0.1, '(0 4)']]\n",
      "state:  (0, 3) , action:  R , transitions:  [[0.7, '(0 4)'], [0.1, '(0 3)'], [0.1, '(0 2)'], [0.1, '(1 3)']]\n",
      "state:  (0, 4) , action:  U , transitions:  [[0.7, '(0 4)'], [0.1, '(0 3)'], [0.1, '(1 4)'], [0.1, '(0 5)']]\n",
      "state:  (0, 4) , action:  L , transitions:  [[0.7, '(0 3)'], [0.1, '(0 4)'], [0.1, '(1 4)'], [0.1, '(0 5)']]\n",
      "state:  (0, 4) , action:  D , transitions:  [[0.7, '(1 4)'], [0.1, '(0 4)'], [0.1, '(0 3)'], [0.1, '(0 5)']]\n",
      "state:  (0, 4) , action:  R , transitions:  [[0.7, '(0 5)'], [0.1, '(0 4)'], [0.1, '(0 3)'], [0.1, '(1 4)']]\n",
      "state:  (0, 5) , action:  U , transitions:  [[0.8, '(0 5)'], [0.1, '(0 4)'], [0.1, '(1 5)']]\n",
      "state:  (0, 5) , action:  L , transitions:  [[0.8, '(0 4)'], [0.1, '(0 5)'], [0.1, '(1 5)']]\n",
      "state:  (0, 5) , action:  D , transitions:  [[0.8, '(1 5)'], [0.1, '(0 5)'], [0.1, '(0 4)']]\n",
      "state:  (0, 5) , action:  R , transitions:  [[0.8, '(0 5)'], [0.1, '(0 4)'], [0.1, '(1 5)']]\n",
      "state:  (1, 0) , action:  U , transitions:  [[0.7, '(0 0)'], [0.1, '(1 0)'], [0.1, '(2 0)'], [0.1, '(1 1)']]\n",
      "state:  (1, 0) , action:  L , transitions:  [[0.7, '(1 0)'], [0.1, '(0 0)'], [0.1, '(2 0)'], [0.1, '(1 1)']]\n",
      "state:  (1, 0) , action:  D , transitions:  [[0.7, '(2 0)'], [0.1, '(1 0)'], [0.1, '(0 0)'], [0.1, '(1 1)']]\n",
      "state:  (1, 0) , action:  R , transitions:  [[0.7, '(1 1)'], [0.1, '(1 0)'], [0.1, '(0 0)'], [0.1, '(2 0)']]\n",
      "state:  (1, 1) , action:  U , transitions:  [[0.6, '(0 1)'], [0.1, '(1 1)'], [0.1, '(1 0)'], [0.1, '(2 1)'], [0.1, '(1 2)']]\n",
      "state:  (1, 1) , action:  L , transitions:  [[0.6, '(1 0)'], [0.1, '(1 1)'], [0.1, '(0 1)'], [0.1, '(2 1)'], [0.1, '(1 2)']]\n",
      "state:  (1, 1) , action:  D , transitions:  [[0.6, '(2 1)'], [0.1, '(1 1)'], [0.1, '(0 1)'], [0.1, '(1 0)'], [0.1, '(1 2)']]\n",
      "state:  (1, 1) , action:  R , transitions:  [[0.6, '(1 2)'], [0.1, '(1 1)'], [0.1, '(0 1)'], [0.1, '(1 0)'], [0.1, '(2 1)']]\n",
      "state:  (1, 2) , action:  U , transitions:  [[0.6, '(0 2)'], [0.1, '(1 2)'], [0.1, '(1 1)'], [0.1, '(2 2)'], [0.1, '(1 3)']]\n",
      "state:  (1, 2) , action:  L , transitions:  [[0.6, '(1 1)'], [0.1, '(1 2)'], [0.1, '(0 2)'], [0.1, '(2 2)'], [0.1, '(1 3)']]\n",
      "state:  (1, 2) , action:  D , transitions:  [[0.6, '(2 2)'], [0.1, '(1 2)'], [0.1, '(0 2)'], [0.1, '(1 1)'], [0.1, '(1 3)']]\n",
      "state:  (1, 2) , action:  R , transitions:  [[0.6, '(1 3)'], [0.1, '(1 2)'], [0.1, '(0 2)'], [0.1, '(1 1)'], [0.1, '(2 2)']]\n",
      "state:  (1, 3) , action:  U , transitions:  [[0.6, '(0 3)'], [0.1, '(1 3)'], [0.1, '(1 2)'], [0.1, '(2 3)'], [0.1, '(1 4)']]\n",
      "state:  (1, 3) , action:  L , transitions:  [[0.6, '(1 2)'], [0.1, '(1 3)'], [0.1, '(0 3)'], [0.1, '(2 3)'], [0.1, '(1 4)']]\n",
      "state:  (1, 3) , action:  D , transitions:  [[0.6, '(2 3)'], [0.1, '(1 3)'], [0.1, '(0 3)'], [0.1, '(1 2)'], [0.1, '(1 4)']]\n",
      "state:  (1, 3) , action:  R , transitions:  [[0.6, '(1 4)'], [0.1, '(1 3)'], [0.1, '(0 3)'], [0.1, '(1 2)'], [0.1, '(2 3)']]\n",
      "state:  (1, 4) , action:  U , transitions:  [[0.6, '(0 4)'], [0.1, '(1 4)'], [0.1, '(1 3)'], [0.1, '(2 4)'], [0.1, '(1 5)']]\n",
      "state:  (1, 4) , action:  L , transitions:  [[0.6, '(1 3)'], [0.1, '(1 4)'], [0.1, '(0 4)'], [0.1, '(2 4)'], [0.1, '(1 5)']]\n",
      "state:  (1, 4) , action:  D , transitions:  [[0.6, '(2 4)'], [0.1, '(1 4)'], [0.1, '(0 4)'], [0.1, '(1 3)'], [0.1, '(1 5)']]\n",
      "state:  (1, 4) , action:  R , transitions:  [[0.6, '(1 5)'], [0.1, '(1 4)'], [0.1, '(0 4)'], [0.1, '(1 3)'], [0.1, '(2 4)']]\n",
      "state:  (1, 5) , action:  U , transitions:  [[0.7, '(0 5)'], [0.1, '(1 5)'], [0.1, '(1 4)'], [0.1, '(2 5)']]\n",
      "state:  (1, 5) , action:  L , transitions:  [[0.7, '(1 4)'], [0.1, '(1 5)'], [0.1, '(0 5)'], [0.1, '(2 5)']]\n",
      "state:  (1, 5) , action:  D , transitions:  [[0.7, '(2 5)'], [0.1, '(1 5)'], [0.1, '(0 5)'], [0.1, '(1 4)']]\n",
      "state:  (1, 5) , action:  R , transitions:  [[0.7, '(1 5)'], [0.1, '(0 5)'], [0.1, '(1 4)'], [0.1, '(2 5)']]\n",
      "state:  (2, 0) , action:  U , transitions:  [[0.7, '(1 0)'], [0.1, '(2 0)'], [0.1, '(3 0)'], [0.1, '(2 1)']]\n",
      "state:  (2, 0) , action:  L , transitions:  [[0.7, '(2 0)'], [0.1, '(1 0)'], [0.1, '(3 0)'], [0.1, '(2 1)']]\n",
      "state:  (2, 0) , action:  D , transitions:  [[0.7, '(3 0)'], [0.1, '(2 0)'], [0.1, '(1 0)'], [0.1, '(2 1)']]\n",
      "state:  (2, 0) , action:  R , transitions:  [[0.7, '(2 1)'], [0.1, '(2 0)'], [0.1, '(1 0)'], [0.1, '(3 0)']]\n",
      "state:  (2, 1) , action:  U , transitions:  [[0.6, '(1 1)'], [0.1, '(2 1)'], [0.1, '(2 0)'], [0.1, '(3 1)'], [0.1, '(2 2)']]\n",
      "state:  (2, 1) , action:  L , transitions:  [[0.6, '(2 0)'], [0.1, '(2 1)'], [0.1, '(1 1)'], [0.1, '(3 1)'], [0.1, '(2 2)']]\n",
      "state:  (2, 1) , action:  D , transitions:  [[0.6, '(3 1)'], [0.1, '(2 1)'], [0.1, '(1 1)'], [0.1, '(2 0)'], [0.1, '(2 2)']]\n",
      "state:  (2, 1) , action:  R , transitions:  [[0.6, '(2 2)'], [0.1, '(2 1)'], [0.1, '(1 1)'], [0.1, '(2 0)'], [0.1, '(3 1)']]\n",
      "state:  (2, 2) , action:  U , transitions:  [[0.6, '(1 2)'], [0.1, '(2 2)'], [0.1, '(2 1)'], [0.1, '(3 2)'], [0.1, '(2 3)']]\n",
      "state:  (2, 2) , action:  L , transitions:  [[0.6, '(2 1)'], [0.1, '(2 2)'], [0.1, '(1 2)'], [0.1, '(3 2)'], [0.1, '(2 3)']]\n",
      "state:  (2, 2) , action:  D , transitions:  [[0.6, '(3 2)'], [0.1, '(2 2)'], [0.1, '(1 2)'], [0.1, '(2 1)'], [0.1, '(2 3)']]\n",
      "state:  (2, 2) , action:  R , transitions:  [[0.6, '(2 3)'], [0.1, '(2 2)'], [0.1, '(1 2)'], [0.1, '(2 1)'], [0.1, '(3 2)']]\n",
      "state:  (2, 3) , action:  U , transitions:  [[0.6, '(1 3)'], [0.1, '(2 3)'], [0.1, '(2 2)'], [0.1, '(3 3)'], [0.1, '(2 4)']]\n",
      "state:  (2, 3) , action:  L , transitions:  [[0.6, '(2 2)'], [0.1, '(2 3)'], [0.1, '(1 3)'], [0.1, '(3 3)'], [0.1, '(2 4)']]\n",
      "state:  (2, 3) , action:  D , transitions:  [[0.6, '(3 3)'], [0.1, '(2 3)'], [0.1, '(1 3)'], [0.1, '(2 2)'], [0.1, '(2 4)']]\n",
      "state:  (2, 3) , action:  R , transitions:  [[0.6, '(2 4)'], [0.1, '(2 3)'], [0.1, '(1 3)'], [0.1, '(2 2)'], [0.1, '(3 3)']]\n",
      "state:  (2, 4) , action:  U , transitions:  [[0.6, '(1 4)'], [0.1, '(2 4)'], [0.1, '(2 3)'], [0.1, '(3 4)'], [0.1, '(2 5)']]\n",
      "state:  (2, 4) , action:  L , transitions:  [[0.6, '(2 3)'], [0.1, '(2 4)'], [0.1, '(1 4)'], [0.1, '(3 4)'], [0.1, '(2 5)']]\n",
      "state:  (2, 4) , action:  D , transitions:  [[0.6, '(3 4)'], [0.1, '(2 4)'], [0.1, '(1 4)'], [0.1, '(2 3)'], [0.1, '(2 5)']]\n",
      "state:  (2, 4) , action:  R , transitions:  [[0.6, '(2 5)'], [0.1, '(2 4)'], [0.1, '(1 4)'], [0.1, '(2 3)'], [0.1, '(3 4)']]\n",
      "state:  (2, 5) , action:  U , transitions:  [[0.7, '(1 5)'], [0.1, '(2 5)'], [0.1, '(2 4)'], [0.1, '(3 5)']]\n",
      "state:  (2, 5) , action:  L , transitions:  [[0.7, '(2 4)'], [0.1, '(2 5)'], [0.1, '(1 5)'], [0.1, '(3 5)']]\n",
      "state:  (2, 5) , action:  D , transitions:  [[0.7, '(3 5)'], [0.1, '(2 5)'], [0.1, '(1 5)'], [0.1, '(2 4)']]\n",
      "state:  (2, 5) , action:  R , transitions:  [[0.7, '(2 5)'], [0.1, '(1 5)'], [0.1, '(2 4)'], [0.1, '(3 5)']]\n",
      "state:  (3, 0) , action:  U , transitions:  [[0.7, '(2 0)'], [0.1, '(3 0)'], [0.1, '(4 0)'], [0.1, '(3 1)']]\n",
      "state:  (3, 0) , action:  L , transitions:  [[0.7, '(3 0)'], [0.1, '(2 0)'], [0.1, '(4 0)'], [0.1, '(3 1)']]\n",
      "state:  (3, 0) , action:  D , transitions:  [[0.7, '(4 0)'], [0.1, '(3 0)'], [0.1, '(2 0)'], [0.1, '(3 1)']]\n",
      "state:  (3, 0) , action:  R , transitions:  [[0.7, '(3 1)'], [0.1, '(3 0)'], [0.1, '(2 0)'], [0.1, '(4 0)']]\n",
      "state:  (3, 1) , action:  U , transitions:  [[0.6, '(2 1)'], [0.1, '(3 1)'], [0.1, '(3 0)'], [0.1, '(4 1)'], [0.1, '(3 2)']]\n",
      "state:  (3, 1) , action:  L , transitions:  [[0.6, '(3 0)'], [0.1, '(3 1)'], [0.1, '(2 1)'], [0.1, '(4 1)'], [0.1, '(3 2)']]\n",
      "state:  (3, 1) , action:  D , transitions:  [[0.6, '(4 1)'], [0.1, '(3 1)'], [0.1, '(2 1)'], [0.1, '(3 0)'], [0.1, '(3 2)']]\n",
      "state:  (3, 1) , action:  R , transitions:  [[0.6, '(3 2)'], [0.1, '(3 1)'], [0.1, '(2 1)'], [0.1, '(3 0)'], [0.1, '(4 1)']]\n",
      "state:  (3, 2) , action:  U , transitions:  [[0.6, '(2 2)'], [0.1, '(3 2)'], [0.1, '(3 1)'], [0.1, '(4 2)'], [0.1, '(3 3)']]\n",
      "state:  (3, 2) , action:  L , transitions:  [[0.6, '(3 1)'], [0.1, '(3 2)'], [0.1, '(2 2)'], [0.1, '(4 2)'], [0.1, '(3 3)']]\n",
      "state:  (3, 2) , action:  D , transitions:  [[0.6, '(4 2)'], [0.1, '(3 2)'], [0.1, '(2 2)'], [0.1, '(3 1)'], [0.1, '(3 3)']]\n",
      "state:  (3, 2) , action:  R , transitions:  [[0.6, '(3 3)'], [0.1, '(3 2)'], [0.1, '(2 2)'], [0.1, '(3 1)'], [0.1, '(4 2)']]\n",
      "state:  (3, 3) , action:  U , transitions:  [[0.6, '(2 3)'], [0.1, '(3 3)'], [0.1, '(3 2)'], [0.1, '(4 3)'], [0.1, '(3 4)']]\n",
      "state:  (3, 3) , action:  L , transitions:  [[0.6, '(3 2)'], [0.1, '(3 3)'], [0.1, '(2 3)'], [0.1, '(4 3)'], [0.1, '(3 4)']]\n",
      "state:  (3, 3) , action:  D , transitions:  [[0.6, '(4 3)'], [0.1, '(3 3)'], [0.1, '(2 3)'], [0.1, '(3 2)'], [0.1, '(3 4)']]\n",
      "state:  (3, 3) , action:  R , transitions:  [[0.6, '(3 4)'], [0.1, '(3 3)'], [0.1, '(2 3)'], [0.1, '(3 2)'], [0.1, '(4 3)']]\n",
      "state:  (3, 4) , action:  U , transitions:  [[0.6, '(2 4)'], [0.1, '(3 4)'], [0.1, '(3 3)'], [0.1, '(4 4)'], [0.1, '(3 5)']]\n",
      "state:  (3, 4) , action:  L , transitions:  [[0.6, '(3 3)'], [0.1, '(3 4)'], [0.1, '(2 4)'], [0.1, '(4 4)'], [0.1, '(3 5)']]\n",
      "state:  (3, 4) , action:  D , transitions:  [[0.6, '(4 4)'], [0.1, '(3 4)'], [0.1, '(2 4)'], [0.1, '(3 3)'], [0.1, '(3 5)']]\n",
      "state:  (3, 4) , action:  R , transitions:  [[0.6, '(3 5)'], [0.1, '(3 4)'], [0.1, '(2 4)'], [0.1, '(3 3)'], [0.1, '(4 4)']]\n",
      "state:  (3, 5) , action:  U , transitions:  [[0.7, '(2 5)'], [0.1, '(3 5)'], [0.1, '(3 4)'], [0.1, '(4 5)']]\n",
      "state:  (3, 5) , action:  L , transitions:  [[0.7, '(3 4)'], [0.1, '(3 5)'], [0.1, '(2 5)'], [0.1, '(4 5)']]\n",
      "state:  (3, 5) , action:  D , transitions:  [[0.7, '(4 5)'], [0.1, '(3 5)'], [0.1, '(2 5)'], [0.1, '(3 4)']]\n",
      "state:  (3, 5) , action:  R , transitions:  [[0.7, '(3 5)'], [0.1, '(2 5)'], [0.1, '(3 4)'], [0.1, '(4 5)']]\n",
      "state:  (4, 0) , action:  U , transitions:  [[0.7, '(3 0)'], [0.1, '(4 0)'], [0.1, '(5 0)'], [0.1, '(4 1)']]\n",
      "state:  (4, 0) , action:  L , transitions:  [[0.7, '(4 0)'], [0.1, '(3 0)'], [0.1, '(5 0)'], [0.1, '(4 1)']]\n",
      "state:  (4, 0) , action:  D , transitions:  [[0.7, '(5 0)'], [0.1, '(4 0)'], [0.1, '(3 0)'], [0.1, '(4 1)']]\n",
      "state:  (4, 0) , action:  R , transitions:  [[0.7, '(4 1)'], [0.1, '(4 0)'], [0.1, '(3 0)'], [0.1, '(5 0)']]\n",
      "state:  (4, 1) , action:  U , transitions:  [[0.6, '(3 1)'], [0.1, '(4 1)'], [0.1, '(4 0)'], [0.1, '(5 1)'], [0.1, '(4 2)']]\n",
      "state:  (4, 1) , action:  L , transitions:  [[0.6, '(4 0)'], [0.1, '(4 1)'], [0.1, '(3 1)'], [0.1, '(5 1)'], [0.1, '(4 2)']]\n",
      "state:  (4, 1) , action:  D , transitions:  [[0.6, '(5 1)'], [0.1, '(4 1)'], [0.1, '(3 1)'], [0.1, '(4 0)'], [0.1, '(4 2)']]\n",
      "state:  (4, 1) , action:  R , transitions:  [[0.6, '(4 2)'], [0.1, '(4 1)'], [0.1, '(3 1)'], [0.1, '(4 0)'], [0.1, '(5 1)']]\n",
      "state:  (4, 2) , action:  U , transitions:  [[0.6, '(3 2)'], [0.1, '(4 2)'], [0.1, '(4 1)'], [0.1, '(5 2)'], [0.1, '(4 3)']]\n",
      "state:  (4, 2) , action:  L , transitions:  [[0.6, '(4 1)'], [0.1, '(4 2)'], [0.1, '(3 2)'], [0.1, '(5 2)'], [0.1, '(4 3)']]\n",
      "state:  (4, 2) , action:  D , transitions:  [[0.6, '(5 2)'], [0.1, '(4 2)'], [0.1, '(3 2)'], [0.1, '(4 1)'], [0.1, '(4 3)']]\n",
      "state:  (4, 2) , action:  R , transitions:  [[0.6, '(4 3)'], [0.1, '(4 2)'], [0.1, '(3 2)'], [0.1, '(4 1)'], [0.1, '(5 2)']]\n",
      "state:  (4, 3) , action:  U , transitions:  [[0.6, '(3 3)'], [0.1, '(4 3)'], [0.1, '(4 2)'], [0.1, '(5 3)'], [0.1, '(4 4)']]\n",
      "state:  (4, 3) , action:  L , transitions:  [[0.6, '(4 2)'], [0.1, '(4 3)'], [0.1, '(3 3)'], [0.1, '(5 3)'], [0.1, '(4 4)']]\n",
      "state:  (4, 3) , action:  D , transitions:  [[0.6, '(5 3)'], [0.1, '(4 3)'], [0.1, '(3 3)'], [0.1, '(4 2)'], [0.1, '(4 4)']]\n",
      "state:  (4, 3) , action:  R , transitions:  [[0.6, '(4 4)'], [0.1, '(4 3)'], [0.1, '(3 3)'], [0.1, '(4 2)'], [0.1, '(5 3)']]\n",
      "state:  (4, 4) , action:  U , transitions:  [[0.6, '(3 4)'], [0.1, '(4 4)'], [0.1, '(4 3)'], [0.1, '(5 4)'], [0.1, '(4 5)']]\n",
      "state:  (4, 4) , action:  L , transitions:  [[0.6, '(4 3)'], [0.1, '(4 4)'], [0.1, '(3 4)'], [0.1, '(5 4)'], [0.1, '(4 5)']]\n",
      "state:  (4, 4) , action:  D , transitions:  [[0.6, '(5 4)'], [0.1, '(4 4)'], [0.1, '(3 4)'], [0.1, '(4 3)'], [0.1, '(4 5)']]\n",
      "state:  (4, 4) , action:  R , transitions:  [[0.6, '(4 5)'], [0.1, '(4 4)'], [0.1, '(3 4)'], [0.1, '(4 3)'], [0.1, '(5 4)']]\n",
      "state:  (4, 5) , action:  U , transitions:  [[0.7, '(3 5)'], [0.1, '(4 5)'], [0.1, '(4 4)'], [0.1, '(5 5)']]\n",
      "state:  (4, 5) , action:  L , transitions:  [[0.7, '(4 4)'], [0.1, '(4 5)'], [0.1, '(3 5)'], [0.1, '(5 5)']]\n",
      "state:  (4, 5) , action:  D , transitions:  [[0.7, '(5 5)'], [0.1, '(4 5)'], [0.1, '(3 5)'], [0.1, '(4 4)']]\n",
      "state:  (4, 5) , action:  R , transitions:  [[0.7, '(4 5)'], [0.1, '(3 5)'], [0.1, '(4 4)'], [0.1, '(5 5)']]\n",
      "state:  (5, 0) , action:  U , transitions:  [[0.8, '(4 0)'], [0.1, '(5 0)'], [0.1, '(5 1)']]\n",
      "state:  (5, 0) , action:  L , transitions:  [[0.8, '(5 0)'], [0.1, '(4 0)'], [0.1, '(5 1)']]\n",
      "state:  (5, 0) , action:  D , transitions:  [[0.8, '(5 0)'], [0.1, '(4 0)'], [0.1, '(5 1)']]\n",
      "state:  (5, 0) , action:  R , transitions:  [[0.8, '(5 1)'], [0.1, '(5 0)'], [0.1, '(4 0)']]\n",
      "state:  (5, 1) , action:  U , transitions:  [[0.7, '(4 1)'], [0.1, '(5 1)'], [0.1, '(5 0)'], [0.1, '(5 2)']]\n",
      "state:  (5, 1) , action:  L , transitions:  [[0.7, '(5 0)'], [0.1, '(5 1)'], [0.1, '(4 1)'], [0.1, '(5 2)']]\n",
      "state:  (5, 1) , action:  D , transitions:  [[0.7, '(5 1)'], [0.1, '(4 1)'], [0.1, '(5 0)'], [0.1, '(5 2)']]\n",
      "state:  (5, 1) , action:  R , transitions:  [[0.7, '(5 2)'], [0.1, '(5 1)'], [0.1, '(4 1)'], [0.1, '(5 0)']]\n",
      "state:  (5, 2) , action:  U , transitions:  [[0.7, '(4 2)'], [0.1, '(5 2)'], [0.1, '(5 1)'], [0.1, '(5 3)']]\n",
      "state:  (5, 2) , action:  L , transitions:  [[0.7, '(5 1)'], [0.1, '(5 2)'], [0.1, '(4 2)'], [0.1, '(5 3)']]\n",
      "state:  (5, 2) , action:  D , transitions:  [[0.7, '(5 2)'], [0.1, '(4 2)'], [0.1, '(5 1)'], [0.1, '(5 3)']]\n",
      "state:  (5, 2) , action:  R , transitions:  [[0.7, '(5 3)'], [0.1, '(5 2)'], [0.1, '(4 2)'], [0.1, '(5 1)']]\n",
      "state:  (5, 3) , action:  U , transitions:  [[0.7, '(4 3)'], [0.1, '(5 3)'], [0.1, '(5 2)'], [0.1, '(5 4)']]\n",
      "state:  (5, 3) , action:  L , transitions:  [[0.7, '(5 2)'], [0.1, '(5 3)'], [0.1, '(4 3)'], [0.1, '(5 4)']]\n",
      "state:  (5, 3) , action:  D , transitions:  [[0.7, '(5 3)'], [0.1, '(4 3)'], [0.1, '(5 2)'], [0.1, '(5 4)']]\n",
      "state:  (5, 3) , action:  R , transitions:  [[0.7, '(5 4)'], [0.1, '(5 3)'], [0.1, '(4 3)'], [0.1, '(5 2)']]\n",
      "state:  (5, 4) , action:  U , transitions:  [[0.7, '(4 4)'], [0.1, '(5 4)'], [0.1, '(5 3)'], [0.1, '(5 5)']]\n",
      "state:  (5, 4) , action:  L , transitions:  [[0.7, '(5 3)'], [0.1, '(5 4)'], [0.1, '(4 4)'], [0.1, '(5 5)']]\n",
      "state:  (5, 4) , action:  D , transitions:  [[0.7, '(5 4)'], [0.1, '(4 4)'], [0.1, '(5 3)'], [0.1, '(5 5)']]\n",
      "state:  (5, 4) , action:  R , transitions:  [[0.7, '(5 5)'], [0.1, '(5 4)'], [0.1, '(4 4)'], [0.1, '(5 3)']]\n",
      "state:  (5, 5) , action:  U , transitions:  [[0.8, '(4 5)'], [0.1, '(5 5)'], [0.1, '(5 4)']]\n",
      "state:  (5, 5) , action:  L , transitions:  [[0.8, '(5 4)'], [0.1, '(5 5)'], [0.1, '(4 5)']]\n",
      "state:  (5, 5) , action:  D , transitions:  [[0.8, '(5 5)'], [0.1, '(4 5)'], [0.1, '(5 4)']]\n",
      "state:  (5, 5) , action:  R , transitions:  [[0.8, '(5 5)'], [0.1, '(4 5)'], [0.1, '(5 4)']]\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    " format of transitions:\n",
    " (x,y) = {\"R: [prob, (x1, y1)]\"}\n",
    "'''\n",
    "for state in states:\n",
    "    for action in actions:\n",
    "        count = 0.0\n",
    "        # just sum = state + actions[action]\n",
    "        # u_sum = [sum(x) for x in zip(state, actions[action])]\n",
    "        result = tuple(( sum(x) for x in zip(state, actions[action]))  )        \n",
    "        # transitions\n",
    "        # print('state: ', state, ', action: ', actions[action], ', u_sum: ', u_sum, ', result', result)\n",
    "        T = []\n",
    "        if result in states:\n",
    "            T.append(build_actions(result, 0.0))\n",
    "            T.append(build_actions(state, 0.1))\n",
    "            # for any action (if result in the state space) we increase count  \n",
    "            count += 0.1  \n",
    "        else:\n",
    "            T.append(build_actions(state, 0.0)) \n",
    "            \n",
    "        for a in actions:\n",
    "            if (a != action):\n",
    "                result2 = tuple( (sum(x) for x in zip(state, actions[a])) ) \n",
    "                #print('result2: ', result2, ', a: ', a, ', action: ', action)\n",
    "                if result2 in states:\n",
    "                    count += 0.1\n",
    "                    T.append(build_actions(result2, 0.1))\n",
    "        T[0][0] = 1.0 - count\n",
    "        \n",
    "        transitions[\"({} {})\".format(*state)][action] = T\n",
    "        print('state: ', state, ', action: ', action, ', transitions: ', T)\n",
    "\n",
    "        \n",
    "#transitions        \n",
    "transitions[\"(5 5)\"] = {\"EXIT\":[(0.0, \"(5 5)\")]}\n",
    "#print(transitions)                                  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Construct environment\n",
    "\n",
    "**mdp = Markov Decision Process**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class mdp:\n",
    "    def __init__(self, transitions, rewards):\n",
    "        self.transitions = transitions\n",
    "        self.rewards = rewards\n",
    "        self.states = transitions.keys()\n",
    "        \n",
    "    def get_rewards(self, state):\n",
    "        return self.rewards[state]\n",
    "        \n",
    "    def get_actions(self, state):\n",
    "        return self.transitions[state].keys()\n",
    "    \n",
    "    def get_transitions(self, state, action):\n",
    "        return self.transitions[state][action]\n",
    "                                       \n",
    "environment = mdp(transitions, rewards)         "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### getting rewards, actions, transitions for 4 different states"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "state:  (0 0)\n",
      "state:  (0 0) , rewards:  -1\n",
      "state:  (0 0) , action:  U , transition:  [[0.8, '(0 0)'], [0.1, '(1 0)'], [0.1, '(0 1)']]\n",
      "state:  (0 0) , action:  L , transition:  [[0.8, '(0 0)'], [0.1, '(1 0)'], [0.1, '(0 1)']]\n",
      "state:  (0 0) , action:  D , transition:  [[0.8, '(1 0)'], [0.1, '(0 0)'], [0.1, '(0 1)']]\n",
      "state:  (0 0) , action:  R , transition:  [[0.8, '(0 1)'], [0.1, '(0 0)'], [0.1, '(1 0)']]\n",
      "state:  (1 3)\n",
      "state:  (1 3) , rewards:  -2\n",
      "state:  (1 3) , action:  U , transition:  [[0.6, '(0 3)'], [0.1, '(1 3)'], [0.1, '(1 2)'], [0.1, '(2 3)'], [0.1, '(1 4)']]\n",
      "state:  (1 3) , action:  L , transition:  [[0.6, '(1 2)'], [0.1, '(1 3)'], [0.1, '(0 3)'], [0.1, '(2 3)'], [0.1, '(1 4)']]\n",
      "state:  (1 3) , action:  D , transition:  [[0.6, '(2 3)'], [0.1, '(1 3)'], [0.1, '(0 3)'], [0.1, '(1 2)'], [0.1, '(1 4)']]\n",
      "state:  (1 3) , action:  R , transition:  [[0.6, '(1 4)'], [0.1, '(1 3)'], [0.1, '(0 3)'], [0.1, '(1 2)'], [0.1, '(2 3)']]\n",
      "state:  (1 4)\n",
      "state:  (1 4) , rewards:  -1\n",
      "state:  (1 4) , action:  U , transition:  [[0.6, '(0 4)'], [0.1, '(1 4)'], [0.1, '(1 3)'], [0.1, '(2 4)'], [0.1, '(1 5)']]\n",
      "state:  (1 4) , action:  L , transition:  [[0.6, '(1 3)'], [0.1, '(1 4)'], [0.1, '(0 4)'], [0.1, '(2 4)'], [0.1, '(1 5)']]\n",
      "state:  (1 4) , action:  D , transition:  [[0.6, '(2 4)'], [0.1, '(1 4)'], [0.1, '(0 4)'], [0.1, '(1 3)'], [0.1, '(1 5)']]\n",
      "state:  (1 4) , action:  R , transition:  [[0.6, '(1 5)'], [0.1, '(1 4)'], [0.1, '(0 4)'], [0.1, '(1 3)'], [0.1, '(2 4)']]\n",
      "state:  (5 5)\n",
      "state:  (5 5) , rewards:  10\n",
      "state:  (5 5) , action:  EXIT , transition:  [(0.0, '(5 5)')]\n"
     ]
    }
   ],
   "source": [
    "for s in ('(0 0)', '(1 3)', '(1 4)', '(5 5)'):\n",
    "    print('state: ', s)\n",
    "    rewards = environment.get_rewards(s)\n",
    "    actions = environment.get_actions(s)    \n",
    "    print('state: ', s, ', rewards: ', rewards)\n",
    "    for a in actions:\n",
    "        trans = environment.get_transitions(s, a)\n",
    "        print('state: ', s, ', action: ', a, ', transition: ', trans)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### get all states from environment\n",
    "\n",
    "**For each stste, actions = dict_keys(['D', 'L', 'R', 'U'])**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "states:  dict_keys(['(0 4)', '(0 3)', '(3 1)', '(4 4)', '(5 2)', '(0 2)', '(2 2)', '(1 1)', '(2 4)', '(5 0)', '(1 3)', '(3 5)', '(1 5)', '(1 2)', '(3 2)', '(4 3)', '(2 3)', '(3 4)', '(1 4)', '(5 5)', '(2 1)', '(4 0)', '(4 2)', '(0 1)', '(0 0)', '(3 0)', '(1 0)', '(2 0)', '(5 3)', '(2 5)', '(0 5)', '(5 4)', '(4 5)', '(4 1)', '(3 3)', '(5 1)'])\n"
     ]
    }
   ],
   "source": [
    "states = environment.states\n",
    "print('states: ', states)\n",
    "\n",
    "# For each stste, actions = dict_keys(['D', 'L', 'R', 'U'])\n",
    "actions = environment.get_actions\n",
    "    \n",
    "V1 = {s:0 for s in states}\n",
    "\n",
    "#for k in V1.keys():\n",
    "#    print('state: ', k, ', value: ', V1.get(k))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Calculate value function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "state:  (0 4) , j:  48\n",
      "state:  (0 3) , j:  48\n",
      "state:  (3 1) , j:  48\n",
      "state:  (4 4) , j:  48\n",
      "state:  (5 2) , j:  48\n",
      "state:  (0 2) , j:  48\n",
      "state:  (2 2) , j:  48\n",
      "state:  (1 1) , j:  48\n",
      "state:  (2 4) , j:  48\n",
      "state:  (5 0) , j:  48\n",
      "state:  (1 3) , j:  48\n",
      "state:  (3 5) , j:  48\n",
      "state:  (1 5) , j:  48\n",
      "state:  (1 2) , j:  48\n",
      "state:  (3 2) , j:  48\n",
      "state:  (4 3) , j:  48\n",
      "state:  (2 3) , j:  48\n",
      "state:  (3 4) , j:  48\n",
      "state:  (1 4) , j:  48\n",
      "state:  (5 5) , j:  48\n",
      "state:  (2 1) , j:  48\n",
      "state:  (4 0) , j:  48\n",
      "state:  (4 2) , j:  48\n",
      "state:  (0 1) , j:  48\n",
      "state:  (0 0) , j:  48\n",
      "state:  (3 0) , j:  48\n",
      "state:  (1 0) , j:  48\n",
      "state:  (2 0) , j:  48\n",
      "state:  (5 3) , j:  48\n",
      "state:  (2 5) , j:  48\n",
      "state:  (0 5) , j:  48\n",
      "state:  (5 4) , j:  48\n",
      "state:  (4 5) , j:  48\n",
      "state:  (4 1) , j:  48\n",
      "state:  (3 3) , j:  48\n",
      "state:  (5 1) , j:  48\n"
     ]
    }
   ],
   "source": [
    "def value_iteration(env):\n",
    "    states = env.states\n",
    "    actions = env.get_actions\n",
    "    \n",
    "    # T and R are just short names for functions get_transition and get_rewards\n",
    "    T = env.get_transitions\n",
    "    R = env.get_rewards\n",
    "        \n",
    "    gamma = 0.9\n",
    "    ep = 0.00001\n",
    "    \n",
    "    #initialize value of all the states to 0 (this is k=0 case)\n",
    "    V1 = {s: 0 for s in states}\n",
    "#    V1 = {s:0 for s in states}\n",
    "\n",
    "    j = {s: 0 for s in states}\n",
    "    while True:\n",
    "        V = V1.copy()\n",
    "        delta = 0\n",
    "        \n",
    "        # Bellman Equation, update the utility values\n",
    "        # \n",
    "        for s in states:\n",
    "            V1[s] = R(s) + gamma * max ([ sum([p * V[s1] for (p, s1) in T(s, a)]) for a in actions(s) ])\n",
    "            delta = max(delta, abs(V1[s] - V[s]))\n",
    "            j[s] += 1\n",
    "            #if (j[s]%5 == 0):\n",
    "            #print('state: ', s, ', j: ', j[s])\n",
    "        \n",
    "        if (delta < ep):\n",
    "            for s in states:\n",
    "                print('state: ', s, ', j: ', j[s])\n",
    "            return V        \n",
    "\n",
    "V = value_iteration(environment)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "state:  (0 4) , value:  -3.7486264440810246\n",
      "state:  (0 3) , value:  -4.770737051713192\n",
      "state:  (5 2) , value:  -0.31668663108289197\n",
      "state:  (2 2) , value:  -4.364990970458393\n",
      "state:  (4 0) , value:  -4.542683567254167\n",
      "state:  (1 2) , value:  -5.498912889345984\n",
      "state:  (3 2) , value:  -3.0158767690643606\n",
      "state:  (4 3) , value:  0.746074968598202\n",
      "state:  (2 3) , value:  -3.9611131189397564\n",
      "state:  (4 5) , value:  6.386273068417885\n",
      "state:  (5 5) , value:  10.0\n",
      "state:  (0 0) , value:  -7.254045926433908\n",
      "state:  (4 2) , value:  -2.4269003539758436\n",
      "state:  (1 0) , value:  -6.8303973438319865\n",
      "state:  (2 5) , value:  1.0500077313918674\n",
      "state:  (5 4) , value:  6.381858414451216\n",
      "state:  (1 4) , value:  -2.669767629736012\n",
      "state:  (3 3) , value:  -1.3660070427910673\n",
      "state:  (0 2) , value:  -5.69643678385376\n",
      "state:  (3 1) , value:  -4.394808517503355\n",
      "state:  (4 4) , value:  2.2770154931228763\n",
      "state:  (1 1) , value:  -7.413093545249849\n",
      "state:  (2 4) , value:  -1.151420699270091\n",
      "state:  (1 3) , value:  -5.189499667327498\n",
      "state:  (3 5) , value:  3.4064124945759247\n",
      "state:  (1 5) , value:  -0.9656083600905481\n",
      "state:  (3 4) , value:  -0.20019185845863774\n",
      "state:  (5 1) , value:  -2.0853565870255877\n",
      "state:  (2 1) , value:  -5.468489694947526\n",
      "state:  (5 0) , value:  -4.2970318841159845\n",
      "state:  (0 1) , value:  -7.592090417532568\n",
      "state:  (3 0) , value:  -6.301197493558509\n",
      "state:  (2 0) , value:  -6.183512582193748\n",
      "state:  (0 5) , value:  -3.3325440173476277\n",
      "state:  (4 1) , value:  -3.4603173995960446\n",
      "state:  (5 3) , value:  3.361775445087509\n"
     ]
    }
   ],
   "source": [
    "#print(value_iteration(environment))\n",
    "\n",
    "V = value_iteration(environment)\n",
    "for k in V.keys():\n",
    "    print('state: ', k, ', value: ', V.get(k))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. Get policy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def policy(env):\n",
    "    states= env.states\n",
    "    actions= env.get_actions\n",
    "    T = env.get_transitions\n",
    "    V = value_iteration(env)\n",
    "    \n",
    "    \n",
    "    P={}\n",
    "    for s in states:\n",
    "        P[s] = max(actions(s),  key= lambda a:sum([p*V[s1]  for (p,s1) in T(s,a)]))\n",
    "    return P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "type policy:  <class 'dict'> , type of P.keys():  <class 'dict_keys'>\n",
      "key:  (0 0) , best action:  D\n",
      "key:  (0 1) , best action:  R\n",
      "key:  (0 2) , best action:  R\n",
      "key:  (0 3) , best action:  R\n",
      "key:  (0 4) , best action:  D\n",
      "key:  (0 5) , best action:  D\n",
      "key:  (1 0) , best action:  D\n",
      "key:  (1 1) , best action:  D\n",
      "key:  (1 2) , best action:  D\n",
      "key:  (1 3) , best action:  R\n",
      "key:  (1 4) , best action:  R\n",
      "key:  (1 5) , best action:  D\n",
      "key:  (2 0) , best action:  R\n",
      "key:  (2 1) , best action:  R\n",
      "key:  (2 2) , best action:  D\n",
      "key:  (2 3) , best action:  R\n",
      "key:  (2 4) , best action:  R\n",
      "key:  (2 5) , best action:  D\n",
      "key:  (3 0) , best action:  R\n",
      "key:  (3 1) , best action:  R\n",
      "key:  (3 2) , best action:  R\n",
      "key:  (3 3) , best action:  D\n",
      "key:  (3 4) , best action:  R\n",
      "key:  (3 5) , best action:  D\n",
      "key:  (4 0) , best action:  R\n",
      "key:  (4 1) , best action:  D\n",
      "key:  (4 2) , best action:  R\n",
      "key:  (4 3) , best action:  D\n",
      "key:  (4 4) , best action:  R\n",
      "key:  (4 5) , best action:  D\n",
      "key:  (5 0) , best action:  R\n",
      "key:  (5 1) , best action:  R\n",
      "key:  (5 2) , best action:  R\n",
      "key:  (5 3) , best action:  R\n",
      "key:  (5 4) , best action:  R\n",
      "key:  (5 5) , best action:  EXIT\n"
     ]
    }
   ],
   "source": [
    "P = policy(environment)\n",
    "\n",
    "print('type policy: ', type(P), ', type of P.keys(): ', type(P.keys()))\n",
    "sorted_keys = sorted(P.keys())\n",
    "for k in sorted_keys:\n",
    "    print('key: ', k, ', best action: ', P[k])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](policy_6x6.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:Anaconda_3]",
   "language": "python",
   "name": "conda-env-Anaconda_3-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
